// Created by WXX on 2021/12/14 21:00
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

/**
 * 执行用时：744 ms, 在所有 C++ 提交中击败了57.38%的用户
 * 内存消耗：211 MB, 在所有 C++ 提交中击败了60.11%的用户
 */
typedef unsigned long long ULL;

const int N = 100010, P = 131;

ULL p[N], h[N];

class Solution {
public:
    int start, n;

    ULL get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    bool check(int len) {
        unordered_set<ULL> S;
        for (int i = 1; i + len - 1 <= n; i++) {
            ULL v = get(i, i + len - 1);
            if (S.count(v)) {
                start = i;
                return true;
            }
            S.insert(v);
        }
        return false;
    }

    string longestDupSubstring(string s) {
        n = s.size();

        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s[i - 1];
        }

        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid))l = mid;
            else r = mid - 1;
        }
        check(r);
        return s.substr(start - 1, r);
    }
};

int main() {

    cout << Solution().longestDupSubstring("banana") << endl;  // ana
    cout << Solution().longestDupSubstring("abcd") << endl;  //

    return 0;
}
